#include <any>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;

#define BUG 123

class heap {
  vector<int> data;
  int heapsize;
  int fatherpos(int pos) { return (pos - 1) >> 1; }
  int leftkid(int pos) { return (pos << 1) + 1; }
  int rightkid(int pos) { return (pos << 1) + 2; }

public:
  heap() : heapsize(0) {}
  virtual ~heap() {}
  int add(int nums);
  int insert(int pos);
  int heapify(int pos);
};

int heap::heapify(int pos) {
  if (pos < 0 || pos >= heapsize) {
    return 1;
  }
  while (pos < heapsize) {
    int largek = -1;
    int lk = leftkid(pos);
    if (lk >= heapsize) {
      break;
    }
    int rk = lk + 1;
    if (rk >= heapsize) {
      largek = lk;
    } else {
      largek = (data[lk] > data[rk]) ? lk : rk;
    }
    if (data[pos] < data[largek]) {
      swap(data[pos], data[largek]);
      //交换下去，对下面的数执行heapify
      pos = largek;
    } else {
      break;
    }
  }
  return 0;
}

int heap::add(int nums) {
  data.push_back(nums);
  ++heapsize;
  int pos = data.size() - 1;
  while ((pos > 0) && (nums > data[fatherpos(pos)])) {
    swap(data[pos], data[fatherpos(pos)]);
    pos = fatherpos(pos);
  }
  return 0;
}

int heap::insert(int pos) {
  if (pos < 0 || pos >= data.size()) {
    return 1;
  }
  while ((pos > 0) && (data[pos] > data[fatherpos(pos)])) {
    swap(data[pos], data[fatherpos(pos)]);
    pos = fatherpos(pos);
  }
  return 0;
}

int main() {
  heap a;
  a.add(1);
  a.add(2);
  a.add(3);
  a.heapify(2);
  cout<<"ff"<<endl;  
}
